import java.util.Arrays;

/**
 * @作者 zxy
 * @时间 2023-04-24 17:10
 * @说明 846. 一手顺子
 * Alice 手中有一把牌，她想要重新排列这些牌，分成若干组，使每一组的牌数都是 groupSize ，并且由 groupSize 张连续的牌组成。
 * 给你一个整数数组 hand 其中 hand[i] 是写在第 i 张牌，和一个整数 groupSize 。如果她可能重新排列这些牌，返回 true ；否则，返回 false 。
 * 示例 1：
 * 输入：hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
 * 输出：true
 * 解释：Alice 手中的牌可以被重新排列为 [1,2,3]，[2,3,4]，[6,7,8]。
 * 示例 2：
 * 输入：hand = [1,2,3,4,5], groupSize = 4
 * 输出：false
 * 解释：Alice 手中的牌无法被重新排列成几个大小为 4 的组。
 */
public class Solution {
    public static void main(String[] args) {
//        new Solution().isNStraightHand(new int[]{1, 2, 3, 6, 2, 3, 4, 7, 8}, 3);
//        new Solution().isNStraightHand(new int[]{1, 1, 2, 2, 3, 3}, 2);
        new Solution().isNStraightHand(new int[]{1, 1, 2, 2, 3, 3}, 3);
    }

    /**
     * 执行用时：8 ms, 在所有 Java 提交中击败了99.20%的用户
     * 内存消耗： 42.4 MB, 在所有 Java 提交中击败了51.20%的用户
     * @param hand
     * @param groupSize
     * @return
     */
    public boolean isNStraightHand(int[] hand, int groupSize) {
        if (hand.length % groupSize != 0) return false;
        Arrays.sort(hand);
        int nowNum = -1;
        int recNum = 0;
        int nextIndex = -1;
        for (int i = 0; i < hand.length; i++) {
            if (recNum == groupSize) {
                nowNum = -1;
                if (nextIndex != -1) {
                    i = nextIndex;
                    nextIndex = -1;
                }
                i--;
                recNum = 0;
            } else if (nowNum == -1) {
                nowNum = hand[i];
                hand[i] = -1;
                recNum++;
            } else if (hand[i] != -1) {
                if (hand[i] == nowNum + 1) {
                    nowNum = hand[i];
                    hand[i] = -1;
                    recNum++;
                } else if (hand[i] < nowNum + 1) {
                    if (nextIndex == -1)
                        nextIndex = i;
                } else return false;
            }
        }
        for (int i = 0; i < hand.length; i++) {
            if (hand[i] != -1) return false;
        }
        return true;
    }
}
